package org.example;

import java.util.*;
import java.util.Arrays;

// 二叉堆核心原理及可视化
// labuladong:https://labuladong.online/algo/data-structure-basic/binary-heap-basic/
// 二叉堆/优先级队列代码实现
// labuladong:https://labuladong.online/algo/data-structure-basic/binary-heap-implement/
// 【练习】优先级队列经典习题
// labuladong:https://labuladong.online/algo/problem-set/binary-heap/
public class PriorityQueue1 {
    // 【二叉堆核心原理及可视化】
    // 二叉堆是一种能够动态排序的数据结构，是二叉树结构的延伸
    // 二叉堆的主要操作就两个，sink（下沉）和swim（上浮），用以维护二叉堆的性质
    // 二叉堆的主要应用有两个，首先是一种很有用的数据结构优先级队列(Priority Queue)，第二是一种排序方法堆排序（Heap Sort）

    // 二叉堆的性质
    // 二叉堆就是一种能够动态排序的数据结构。所谓动态排序，就是说我们可以不断往数据结构里面添加或删除元素，数据结构会自动调整元素的位置，
    // 使得我们可以有序地从数据结构中读取元素，这是一般的排序算法做不到的。

    // 能动态排序的常用数据结构其实只有两个，一个是优先级队列（底层用二叉堆实现），另一个是二叉搜索树。
    // 二叉搜索树的用途更广泛，优先级队列能做的事情，二叉搜索树其实都能做。
    // 但优先级队列的 API 和代码实现相较于二叉搜索树更简单，所以一般能用优先级队列解决的问题，我们没必要用二叉搜索树。
    // 二叉堆是怎么做到动态排序的呢？这就要说到二叉堆这种结构的性质了。

    // 二叉堆的性质
    // 你可以认为二叉堆是一种特殊的二叉树，这棵二叉树上的任意节点的值，都必须大于等于（或小于等于）其左右子树所有节点的值。
    // 如果是大于等于，我们称之为「大顶堆」，如果是小于等于，我们称之为「小顶堆」。
    // 对于小顶堆，每个节点下方的所有节点的值都比它大，那么不难想象根节点就是整棵树上的最小值。
    // 同理，大顶堆的根节点就是整棵树上的最大值。所以二叉堆可以辅助我们快速找到最大值或最小值。
    // 二叉堆还有个性质：一个二叉堆的左右子堆（子树）也是一个二叉堆。这个性质主要在
    // 堆排序算法的优化 中有用到。

    // 【最常见的应用：优先级队列】
    static class MyPriorityQueue1 {
        // 在二叉堆堆顶插入一个元素，时间复杂度 O(logN)
        // N 为当前二叉堆中的元素个数
        void push(int x) {
        }

        // 返回堆顶元素，时间复杂度 O(1)
        // 该堆顶元素就是二叉堆中的最大值或最小值，取决于是最大堆还是最小堆
        int peek() {
            return -1;
        }

        // 删除堆顶元素，时间复杂度 O(logN)
        int pop() {
            return -1;
        }

        // 返回堆中元素的个数，时间复杂度 O(1)
        int size() {
            return -1;
        }
        // 当然，自动排序是有代价的，注意优先级队列 API 的时间复杂度，增删元素的复杂度是 O(logN)，其中 N 是当前二叉堆中的元素个数，
        // 回头在算法题里面用到这种结构的话，你得会计算总的时间复杂度。

        // 为啥叫优先级「队列」？
        // 有的读者可能会问，这明明就是二叉堆，为啥非要叫他优先级队列呢？
        // 主要是因为这个数据结构的 API 和我们之前讲的
        // 标准队列 API 很像，标准队列是先进先出的顺序，而二叉堆可以理解为一种会自动排序的队列，所以叫做优先级队列感觉也挺贴切的。
        // 当然，你也一定要明白，虽然它的 API 像队列，但它的底层原理和二叉树有关，和队列没啥关系。
    }

    // 【另一种应用：堆排序】
    // 这种排序算法其实不用专门去学的。它的原理特别简单，
    // 就相当于把一个乱序的数组都 push 到一个二叉堆（优先级队列）里面，然后再一个个 pop 出来，就得到了一个有序的数组：
    public int[] heapSort(int[] arr) {
        int[] res = new int[arr.length];
        MyPriorityQueue1 pq = new MyPriorityQueue1();
        for (int x : arr) {
            pq.push(x);
        }
        // 元素出堆的顺序是有序的
        for (int i = 0; i < arr.length; i++) {
            res[i] = pq.pop();
        }
        return res;
        // 当然，正常的堆排序算法的代码并不依赖优先级队列，且空间复杂度是 O(1)。
        // 那是因为它把 push 和 pop 的代码逻辑展开了，再加上直接在数组上原地建堆，这样就不需要额外的空间了。
        // 但堆排序的本质还是依靠二叉堆的性质来排序元素，等我手把手带你实现优先级队列之后，你就可以自己实现堆排序了。
    }

    // 【完整版优先级队列】
    static class MyPriorityQueue<T> {
        T[] heap;
        int size;
        final Comparator<? super T> comparator;

        @SuppressWarnings("unchecked")
        public MyPriorityQueue(int capacity, Comparator<? super T> comparator) {
            heap = (T[]) new Object[capacity];
            size = 0;
            this.comparator = comparator;
        }

        public int size() {
            return size;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        // 父节点的索引
        private int parent(int node) {
            return (node - 1) / 2;
        }

        // 左子节点的索引
        private int left(int node) {
            return node * 2 + 1;
        }

        // 右子节点的索引
        private int right(int node) {
            return node * 2 + 2;
        }

        // 交换数组的两个元素
        private void swap(int i, int j) {
            T temp = heap[i];
            heap[i] = heap[j];
            heap[j] = temp;
        }

        // 差，返回堆顶元素，时间复杂度O(1)
        public T peek() {
            if (isEmpty()) {
                throw new NoSuchElementException("Priority queue underflow");
            }
            return heap[0];
        }

        // 增，向堆中插入一个元素，时间复杂度 O(logN)
        public void push(T x) {
            // 扩容
            if (size == heap.length) {
                resize(2 * heap.length);
            }
            // 把新元素追加到最后
            heap[size] = x;
            // 然后上浮到正确位置
            swim(size);
            size++;
        }

        // 删，删除堆顶元素，时间复杂度 O(logN)
        public T pop() {
            if (isEmpty()) {
                throw new NoSuchElementException("Priority queue underflow");
            }
            T res = heap[0];
            // 把堆底元素放到堆顶
            swap(0, size - 1);
            // 避免对象游离
            heap[size - 1] = null;
            size--;
            // 然后下沉到正确位置
            sink(0);
            // 缩容
            if ((size > 0) && (size == heap.length / 4)) {
                resize(heap.length / 2);
            }
            return res;
        }

        // 上浮操作，时间复杂度是树高 O(logN)
        private void swim(int node) {
            while (node > 0 && comparator.compare(heap[parent(node)], heap[node]) > 0) {
                swap(parent(node), node);
                node = parent(node);
            }
        }

        // 下沉操作，时间复杂度是树高 O(logN)
        private void sink(int node) {
            while (left(node) < size || right(node) < size) {
                // 比较自己和左右子节点，看看谁最小
                int min = node;
                if (left(node) < size && comparator.compare(heap[left(node)], heap[min]) < 0) {
                    min = left(node);
                }
                if (right(node) < size && comparator.compare(heap[right(node)], heap[min]) < 0) {
                    min = right(node);
                }
                if (min == node) {
                    break;
                }
                // 如果左右子节点中有比自己小的，就交换
                swap(node, min);
                node = min;
            }
        }

        // 调整堆的大小
        @SuppressWarnings("unchecked")
        private void resize(int capacity) {
            assert capacity > size;
            T[] temp = (T[]) new Object[capacity];
            for (int i = 0; i < size; i++) {
                temp[i] = heap[i];
            }
            heap = temp;
        }

        public static void main(String[] args) {
            MyPriorityQueue<Integer> pq = new MyPriorityQueue<>(3, Comparator.naturalOrder());
            pq.push(3);
            pq.push(1);
            pq.push(4);
            pq.push(1);
            pq.push(5);
            pq.push(9);
            // 1 1 3 4 5 9
            while (!pq.isEmpty()) {
                System.out.println(pq.pop());
            }
        }
    }

    // 【练习】优先级队列经典习题
    // https://labuladong.online/algo/problem-set/binary-heap/#%E8%A7%A3%E6%B3%95%E4%BB%A3%E7%A0%81-3
    // 二叉堆的主要应用是优先级队列，而优先级队列的特色是动态排序，插入的元素可以自动维护正确的顺序。当然，
    // 二叉搜索树 也可以做到动态排序，但优先级队列提供的接口更简单，实现也更简单。
    // 一般来说，用到优先级队列的题目主要分两类，一类是把多个有序序列合并成一个，另一类是在多个有序序列中寻找第 k 个最大元素这类题，我们分别来看。

    // >>>>> 类型一：合并有序序列 <<<<<
    // 23. 合并 K 个升序链表
    // 给你一个链表数组，每个链表都已经按升序排列。
    // 请你将所有链表合并到一个升序链表中，返回合并后的链表。
    // 示例 1：
    // 输入：lists = [[1,4,5],[1,3,4],[2,6]]
    // 输出：[1,1,2,3,4,4,5,6]
    // 解释：链表数组如下：
    // [
    //   1->4->5,
    //   1->3->4,
    //   2->6
    // ]
    // 将它们合并到一个有序链表中得到。
    // 1->1->2->3->4->4->5->6

    static class MergeKLists {
        static class ListNode {
            int val;
            ListNode next;

            ListNode() {
            }

            ListNode(int val) {
                this.val = val;
            }

            ListNode(int val, ListNode next) {
                this.val = val;
                this.next = next;
            }
        }

        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) {
                return null;
            }
            // 虚拟头结点
            ListNode dummy = new ListNode(-1);
            ListNode p = dummy;
            // 优先级队列，最小堆
            PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> (a.val - b.val));
            for (ListNode head : lists) {
                // 只添加了一个头结点
                if (head != null) {
                    pq.add(head);
                }
            }
            while (!pq.isEmpty()) {
                // 获取最小节点，接到结果链表中
                ListNode node = pq.poll();
                p.next = node;
                if (node.next != null) {
                    pq.add(node.next);
                }
                // p指针不断前进
                p = p.next;
            }
            return dummy.next;
        }
    }

    // 373. 查找和最小的 K 对数字
    // 给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
    // 定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
    // 请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。
    // 示例 1:
    // 输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
    // 输出: [1,2],[1,4],[1,6]
    // 解释: 返回序列中的前 3 对数：
    //     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
    static class KSmallestPairs {
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            // 存储三元组（nums1[i], nums2[i], i）
            // i记录nums2元素的索引位置，用于生成下一个节点
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
                // 按照数对的元素和升序排列
                return (a[0] + a[1]) - (b[0] + b[1]);
            });
            // 按照23题的逻辑初始化优先级队列
            for (int i = 0; i < nums1.length; i++) {
                pq.offer(new int[]{nums1[i], nums2[0], 0});
            }
            List<List<Integer>> res = new ArrayList<>();
            // 执行合并多个有序链表的逻辑
            while (!pq.isEmpty() && k > 0) {
                int[] cur = pq.poll();
                k--;
                // 链表中的下一个节点加入优先级队列
                int next_index = cur[2] + 1;
                if (next_index < nums2.length) {
                    pq.add(new int[]{cur[0], nums2[next_index], next_index});
                }
                List<Integer> pair = new ArrayList<>();
                pair.add(cur[0]);
                pair.add(cur[1]);
                res.add(pair);
            }
            return res;
        }
    }

    // 378. 有序矩阵中第 K 小的元素
    // 给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
    // 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
    // 你必须找到一个内存复杂度优于 O(n2) 的解决方案。
    // 示例 1：
    // 输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
    // 输出：13
    // 解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
    static class KthSmallest {
        public int kthSmallest(int[][] matrix, int k) {
            // 存储二元组(matrix[i][j], i, j)
            // i,j 记录当前元素的索引位置，用于生成下一个节点
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
                // 按照元素大小升序排列
                return a[0] - b[0];
            });
            // 初始化优先级队列，把每一行的第一个元素装进去
            for (int i = 0; i < matrix.length; i++) {
                pq.offer(new int[]{matrix[i][0], i, 0});
            }

            int res = 1;
            // 执行合并多个有序列表的逻辑，找到第k小的元素
            while (!pq.isEmpty() && k > 0) {
                int[] cur = pq.poll();
                res = cur[0];
                k--;
                // 链表中的下一个节点加入优先级队列
                int i = cur[1], j = cur[2];
                if (j + 1 < matrix[i].length) {
                    pq.add(new int[]{matrix[i][j + 1], i, j + 1});
                }
            }
            return res;
        }
    }

    // 313. 超级丑数
    // 丑数:就是只包含质因数 2、3 和 5 的 正 整数。
    // 超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。
    //给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。
    //题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
    //示例 1：
    //输入：n = 12, primes = [2,7,13,19]
    //输出：32
    //解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。
    static class NthSuperUglyNumber {
        public int nthSuperUglyNumber(int n, int[] primes) {
            // 优先队列中装三元组int[]{product, prime, pi}
            // 其中product代表链表节点的值，prime是计算下一个节点所需的质数因子，pi代表链表上的指针
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
                return a[0] - b[0];
            });
            // 把多条链表的头结点加入优先级队列
            for (int i = 0; i < primes.length; i++) {
                pq.offer(new int[]{1, primes[i], 1});
            }

            // 可以理解为最终合并的有序列表（结果链表）
            int[] ugly = new int[n + 1];
            // 可以理解为结果链表上的指针
            int p = 1;
            while (p <= n) {
                // 取三个链表的最小节点
                int[] pair = pq.poll();
                int product = pair[0];
                int prime = pair[1];
                int index = pair[2];

                // 避免重复链表出现重复元素
                if (product != ugly[p - 1]) {
                    // 接到结果链表上
                    ugly[p] = product;
                    p++;
                }

                // 生成下一个节点加入优先级队列
                int[] nextPair = new int[]{ugly[index] * prime, prime, index + 1};
                pq.offer(nextPair);
            }
            return ugly[n];
        }
    }

    // 355. 设计推特
    // 设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近 10 条推文。
    //实现 Twitter 类：
    //Twitter() 初始化简易版推特对象
    //void postTweet(int userId, int tweetId) 根据给定的 tweetId 和 userId 创建一条新推文。每次调用此函数都会使用一个不同的 tweetId 。
    //List<Integer> getNewsFeed(int userId) 检索当前用户新闻推送中最近  10 条推文的 ID 。新闻推送中的每一项都必须是由用户关注的人或者是用户自己发布的推文。推文必须 按照时间顺序由最近到最远排序 。
    //void follow(int followerId, int followeeId) ID 为 followerId 的用户开始关注 ID 为 followeeId 的用户。
    //void unfollow(int followerId, int followeeId) ID 为 followerId 的用户不再关注 ID 为 followeeId 的用户。
    //示例：
    //输入
    //["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
    //[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
    //输出
    //[null, null, [5], null, null, [6, 5], null, [5]]
    //解释
    //Twitter twitter = new Twitter();
    //twitter.postTweet(1, 5); // 用户 1 发送了一条新推文 (用户 id = 1, 推文 id = 5)
    //twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文
    //twitter.follow(1, 2);    // 用户 1 关注了用户 2
    //twitter.postTweet(2, 6); // 用户 2 发送了一个新推文 (推文 id = 6)
    //twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5] 。推文 id 6 应当在推文 id 5 之前，因为它是在 5 之后发送的
    //twitter.unfollow(1, 2);  // 用户 1 取消关注了用户 2
    //twitter.getNewsFeed(1);  // 用户 1 获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用户 2

    // 【非常好的一个代码】
    static class Twitter {
        // 全局时间戳
        int globalTime = 0;
        // 记录用户ID到用户实例的映射
        HashMap<Integer, User> idToUser = new HashMap<>();

        // Tweet 类
        class Tweet {
            int id;
            // 时间戳用于对信息流按照时间排序
            int timestamp;
            // 指向吓一跳tweet，类似单链表结构
            Tweet next;

            public Tweet(int id) {
                this.id = id;
                // 新建一条tweet时，记录并更新时间戳
                this.timestamp = globalTime++;
            }
        }

        // 用户类
        class User {
            // 记录该用户的id以及发布的tweet
            int id;
            Tweet tweetHead;
            // 记录该用户的关注者
            HashSet<User> followedUserSet;

            public User(int id) {
                this.id = id;
                this.tweetHead = null;
                this.followedUserSet = new HashSet<>();
            }

            public boolean equals(User other) {
                return this.id == other.id;
            }

            // 关注其他人
            public void follow(User other) {
                followedUserSet.add(other);
            }

            // 取关其他人
            public void unfollow(User other) {
                followedUserSet.remove(other);
            }

            // 发布一条tweet
            public void post(Tweet tweet) {
                // 把新发布的tweet作为链表的头结点
                tweet.next = tweetHead;
                tweetHead = tweet;
            }
        }

        public Twitter() {

        }

        public void postTweet(int userId, int tweetId) {
            // 如果这个用户还不存在，新建用户
            if (!idToUser.containsKey(userId)) {
                idToUser.put(userId, new User(userId));
            }
            User user = idToUser.get(userId);
            user.post(new Tweet(tweetId));
        }

        public List<Integer> getNewsFeed(int userId) {
            List<Integer> res = new LinkedList<>();
            if (!idToUser.containsKey(userId)) {
                return res;
            }
            // 获取用户关注的用户列表
            User user = idToUser.get(userId);
            Set<User> followedUserSet = user.followedUserSet;
            // 每一个用户的tweet是一条按时间排列的链表
            // 现在执行合并多条有序链表的逻辑，找出时间线中的最近10条动态
            PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> {
                // 按照每条tweet的发布时间降序连列（最近发布排在事件流前面）
                return b.timestamp - a.timestamp;
            });
            // 该用户自己的tweet也在时间线内
            if (user.tweetHead != null) {
                pq.offer(user.tweetHead);
            }
            for (User other : followedUserSet) {
                if (other.tweetHead != null) {
                    pq.offer(other.tweetHead);
                }
            }

            // 合并多条有序链表
            int count = 0;
            while (!pq.isEmpty() && count < 10) {
                Tweet tweet = pq.poll();
                res.add(tweet.id);
                if (tweet.next != null) {
                    pq.offer(tweet.next);
                }
                count++;
            }
            return res;
        }

        public void follow(int followerId, int followeeId) {
            if (!idToUser.containsKey(followerId)) {
                idToUser.put(followerId, new User(followerId));
            }
            if (!idToUser.containsKey(followeeId)) {
                idToUser.put(followeeId, new User(followeeId));
            }
            User follower = idToUser.get(followerId);
            User followee = idToUser.get(followeeId);
            // 关注者关注被关注者
            follower.follow(followee);
        }

        public void unfollow(int followerId, int followeeId) {
            if (!idToUser.containsKey(followerId) || !idToUser.containsKey(followeeId)) {
                return;
            }
            User follower = idToUser.get(followerId);
            User followee = idToUser.get(followeeId);
            // 关注者取关被关注者
            follower.unfollow(followee);
        }
    }

    static class Twitter1 {
        // 全局时间戳
        int globalTime = 0;
        // 记录用户ID到用户示例的映射
        HashMap<Integer, User> idToUser = new HashMap<>();

        // Tweet类
        class Tweet {
            private int id;
            // 时间戳用于对信息流按照时间排序
            private int timestamp;
            // 指向下一条tweet，类似单链表结构
            private Tweet next;

            public Tweet(int id) {
                this.id = id;
                // 新建一条tweet时，记录并更新时间戳
                this.timestamp = globalTime++;
            }

            public int getId() {
                return id;
            }

            public void setId(int id) {
                this.id = id;
            }

            public int getTimestamp() {
                return timestamp;
            }

            public void setTimestamp(int timestamp) {
                this.timestamp = timestamp;
            }

            public Tweet getNext() {
                return next;
            }

            public void setNext(Tweet next) {
                this.next = next;
            }
        }

        // 用户类
        class User {
            // 记录该用户的ID以及发布的tweet
            private int id;
            private Tweet tweetHead;
            // 记录该用户的关注者
            private HashSet<User> followedUserSet;

            public User(int id) {
                this.id = id;
                this.tweetHead = null;
                this.followedUserSet = new HashSet<>();
            }

            public int getId() {
                return id;
            }

            public void setId(int id) {
                this.id = id;
            }

            public Tweet getTweetHead() {
                return tweetHead;
            }

            public void setTweetHead(Tweet tweetHead) {
                this.tweetHead = tweetHead;
            }

            public HashSet<User> getFollowedUserSet() {
                return followedUserSet;
            }

            public void setFollowedUserSet(HashSet<User> followedUserSet) {
                this.followedUserSet = followedUserSet;
            }

            // 关注其他人
            public void follow(User other) {
                followedUserSet.add(other);
            }

            // 取关其他人
            public void unfollow(User other) {
                followedUserSet.remove(other);
            }

            // 发布一条tweet
            public void post(Tweet tweet) {
                // 把新发布的tweet作为链表头结点
                tweet.setNext(tweetHead);
                tweetHead = tweet;
            }
        }

        public void postTweet(int userId, int tweetId) {
            // 如果这个用户还不存在，新建用户
            if (!idToUser.containsKey(userId)) {
                idToUser.put(userId, new User(userId));
            }
            User user = idToUser.get(userId);
            user.post(new Tweet(tweetId));
        }

        public List<Integer> getNewsFeed(int userId) {
            List<Integer> res = new LinkedList<>();
            if (!idToUser.containsKey(userId)) {
                return res;
            }
            // 获取该用户关注的用户列表
            User user = idToUser.get(userId);
            Set<User> followedUserSet = user.getFollowedUserSet();
            // 每个用户的tweet是一条按时间排序的链表
            // 现在执行合并多条有序链表的逻辑，找出时间线中的最近10条动态
            PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> {
                // 按照每条tweet的发布时间降序排列（最近发布的排在事件流前面）
                return b.timestamp - a.timestamp;
            });
            // 该用户自己的tweet也在时间线内
            if (user.getTweetHead() != null) {
                pq.offer(user.getTweetHead());
            }
            for (User other : followedUserSet) {
                if (other.getTweetHead() != null) {
                    pq.offer(other.tweetHead);
                }
            }
            // 合并多条有序链表
            int count = 0;
            while (!pq.isEmpty() && count < 10) {
                Tweet tweet = pq.poll();
                res.add(tweet.getId());
                if (tweet.getNext() != null) {
                    pq.offer(tweet.getNext());
                }
                count++;
            }
            return res;
        }

        public void follow(int followerId, int followeeId) {
            if (!idToUser.containsKey(followerId)) {
                idToUser.put(followerId, new User(followerId));
            }
            if (!idToUser.containsKey(followeeId)) {
                idToUser.put(followeeId, new User(followeeId));
            }
            User follower = idToUser.get(followerId);
            User followee = idToUser.get(followeeId);
            // 关注者关注被关注者
            follower.follow(followee);
        }

        public void unfollow(int followerId, int followeeId) {
            if (!idToUser.containsKey(followerId) || !idToUser.containsKey(followeeId)) {
                return;
            }
            User follower = idToUser.get(followerId);
            User followee = idToUser.get(followeeId);
            // 关注者取关被关注者
            follower.unfollow(followee);
        }
    }

    // >>>>> 类型二，寻找第 k 大元素 <<<<<

    // 215. 数组中的第K个最大元素
    // 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
    // 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
    // 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
    // 示例 1:
    // 输入: [3,2,1,5,6,4], k = 2
    // 输出: 5
    // 示例 2:
    // 输入: [3,2,3,1,2,4,5,5,6], k = 4
    // 输出: 4
    // 提示：
    // 1 <= k <= nums.length <= 105
    // -104 <= nums[i] <= 104

    // 基本思路
    // 二叉堆的解法比较简单，实际写算法题的时候，推荐大家写这种解法
    // 可以把小顶堆 pq 理解成一个筛子，较大的元素会沉淀下去，较小的元素会浮上来；当堆大小超过 k 的时候，我们就删掉堆顶的元素，因为这些元素比较小，而我们想要的是前 k 个最大元素嘛。
    // 当 nums 中的所有元素都过了一遍之后，筛子里面留下的就是最大的 k 个元素，而堆顶元素是堆中最小的元素，也就是「第 k 个最大的元素」。
    // 二叉堆插入和删除的时间复杂度和堆中的元素个数有关，在这里我们堆的大小不会超过 k，所以插入和删除元素的复杂度是 O(logK)，再套一层 for 循环，总的时间复杂度就是 O(NlogK)。
    // 当然，这道题可以有效率更高的解法叫「快速选择算法」，只需要 O(N) 的时间复杂度。
    // 快速选择算法不用借助二叉堆结构，而是稍微改造了快速排序的算法思路，有兴趣的读者可以看详细题解。

    static class FindKthLargest {
        public int findKthLargest(int[] nums, int k) {
            // 小顶堆，堆顶是最小元素
            PriorityQueue<Integer> pq = new PriorityQueue<>();
            for (int e : nums) {
                // 每个元素都要过一遍二叉堆
                pq.offer(e);
                // 堆顶元素多余k个时，删除堆顶元素
                if (pq.size() > k) {
                    pq.poll();
                }
            }
            // pq中剩下的是nums中k个最大元素
            // 堆顶元素多于k个时，删除堆顶元素
            return pq.peek();
        }
    }

    // 451. 根据字符出现频率排序
    // 给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
    // 返回 已排序的字符串 。如果有多个答案，返回其中任何一个。
    // 示例 1:
    // 输入: s = "tree"
    // 输出: "eert"
    // 解释: 'e'出现两次，'r'和't'都只出现一次。
    // 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
    // 示例 2:
    // 输入: s = "cccaaa"
    // 输出: "cccaaa"
    // 解释: 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
    // 注意"cacaca"是不正确的，因为相同的字母必须放在一起。
    // 示例 3:
    // 输入: s = "Aabb"
    // 输出: "bbAa"
    // 解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
    // 注意'A'和'a'被认为是两种不同的字符。

    // 做这道题肯定需要计算每个字符出现的频率，然后你可以用很多种其他方法把字符按照频率排序。我这里用
    // 优先级队列 来实现排序的效果，详细看代码。
    static class FrequencySort {
        public String frequencySort(String s) {
            char[] chars = s.toCharArray();
            // s中的字符->该字符出现的频率
            HashMap<Character, Integer> chaToFreq = new HashMap<>();
            for (char ch : chars) {
                chaToFreq.put(ch, chaToFreq.getOrDefault(ch, 0) + 1);
            }

            PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((entry1, entry2) -> {
                // 队列按照键值对中的值（字符出现频率）从大到小排序
                return entry2.getValue().compareTo(entry1.getValue());
            });
            // 按照字符频率排序
            for (Map.Entry<Character, Integer> entry : chaToFreq.entrySet()) {
                pq.offer(entry);
            }
            StringBuilder sb = new StringBuilder();
            while (!pq.isEmpty()) {
                // 把频率最高的字符排在前面
                Map.Entry<Character, Integer> entry = pq.poll();
                // String part = "abc".repeat(3); // part 的值为 "abcabcabc"
                String part = String.valueOf(entry.getKey()).repeat(entry.getValue());
                sb.append(part);
            }
            return sb.toString();
        }
    }

    // 703. 数据流中的第 K 大元素
    // 设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
    // 请实现 KthLargest 类：
    // KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
    // int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
    // 示例：
    // 输入：
    // ["KthLargest", "add", "add", "add", "add", "add"]
    // [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
    // 输出：
    // [null, 4, 5, 5, 8, 8]
    // 解释：
    // KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
    // kthLargest.add(3);   // return 4
    // kthLargest.add(5);   // return 5
    // kthLargest.add(10);  // return 5
    // kthLargest.add(9);   // return 8
    // kthLargest.add(4);   // return 8
    static class KthLargest {
        private int k;
        // 默认是小顶堆
        private PriorityQueue<Integer> pq = new PriorityQueue<>();

        public KthLargest(int k, int[] nums) {
            // 将nums装入小顶堆，保留下前k大的元素
            for (int e : nums) {
                pq.offer(e);
                if (pq.size() > k) {
                    pq.poll();
                }
            }
            this.k = k;
        }

        public int add(int val) {
            // 维护小顶堆只保留前k大的元素
            pq.offer(val);
            if (pq.size() > k) {
                pq.poll();
            }
            // 堆顶就是第k大元素（即倒数第k小的元素）
            return pq.peek();
        }
    }

    // 347. 前 K 个高频元素
    // 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
    // 示例 1:
    // 输入: nums = [1,1,1,2,2,3], k = 2
    // 输出: [1,2]
    // 示例 2:
    // 输入: nums = [1], k = 1
    // 输出: [1]

    // 基本思路
    // 首先，肯定要用一个valToFreq哈希表把每个元素出现的频率计算出来
    // 然后，这道题就变成了 215. 数组中的第 K 个最大元素，只不过第 215 题让你求数组中元素值 e 排在第 k 大的那个元素，
    // 这道题让你求数组中元素值 valToFreq[e] 排在前 k 个的元素。
    // 我在 快速排序详解及运用 中讲过第 215 题，可以用
    // 优先级队列 或者快速选择算法解决这道题。这里稍微改一下优先级队列的比较函数，或者改一下快速选择算法中的逻辑即可。

    // 用优先级队列解决这道题
    static class TopKFrequent1 {
        public int[] topKFrequent(int[] nums, int k) {
            // nums中的元素->该元素出现的频率
            HashMap<Integer, Integer> valToFreq = new HashMap<>();
            for (int v : nums) {
                valToFreq.put(v, valToFreq.getOrDefault(v, 0) + 1);
            }
            PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((entry1, entry2) -> {
                // 队列按照键值对中的值（元素出现频率）从小到大排序
                return entry1.getValue().compareTo(entry2.getValue());
            });
            for (Map.Entry<Integer, Integer> entry : valToFreq.entrySet()) {
                pq.offer(entry);
                if (pq.size() > k) {
                    // 弹出最小元素，维护队列内是k个频率最大的元素
                    pq.poll();
                }
            }
            int[] res = new int[k];
            for (int i = k - 1; i >= 0; i--) {
                // res数组中存储前k个最大元素
                res[i] = pq.poll().getKey();
            }
            return res;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 1, 1, 2, 2, 3};
        int k = 2;
        new TopKFrequent1().topKFrequent(nums, k);
    }

    // 用计数排序方法解决这道题
    static class TopKFrequent2 {
        public int[] topKFrequent(int[] nums, int k) {
            // nums中的元素->该元素出现的频率
            HashMap<Integer, Integer> valToFreq = new HashMap<>();
            for (int v : nums) {
                valToFreq.put(v, valToFreq.getOrDefault(v, 0) + 1);
            }
            // 频率->这个频率有哪些元素
            ArrayList<Integer>[] freqToVals = new ArrayList[nums.length + 1];
            for (int key : valToFreq.keySet()) {
                int freq = valToFreq.get(key);
                if (freqToVals[freq] == null) {
                    freqToVals[freq] = new ArrayList<>();
                }
                freqToVals[freq].add(key);
            }

            int[] res = new int[k];
            int p = 0;
            // freqToVals从后往前存储着出现最多的元素
            for (int i = freqToVals.length - 1; i > 0; i--) {
                ArrayList<Integer> valList = freqToVals[i];
                if (valList == null) {
                    continue;
                }
                for (int j = 0; j < valList.size(); j++) {
                    // 将出现次数最多的k个元素装入res
                    res[p] = valList.get(j);
                    p++;
                    if (p == k) {
                        return res;
                    }
                }
            }
            return null;
        }
    }

    // 692. 前K个高频单词
    // 给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
    // 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
    // 示例 1：
    // 输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
    // 输出: ["i", "love"]
    // 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    //    注意，按字母顺序 "i" 在 "love" 之前。
    // 示例 2：
    // 输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
    // 输出: ["the", "is", "sunny", "day"]
    // 解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    //    出现次数依次为 4, 3, 2 和 1 次。
    static class TopKFrequent {
        public List<String> topKFrequent(String[] words, int k) {
            // 字符串->该字符串出现的频率
            HashMap<String, Integer> wordToFreq = new HashMap<>();
            for (String word : words) {
                wordToFreq.put(word, wordToFreq.getOrDefault(word, 0) + 1);
            }
            PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>((entry1, entry2) -> {
                if (entry1.getValue().equals(entry2.getValue())) {
                    // 如果出现频率像童话，按照字符串字典序排序
                    return entry2.getKey().compareTo(entry1.getKey());
                }
                // 队列按照字符串出现频率从小到大排序
                return entry1.getValue().compareTo(entry2.getValue());
            });
            // 按照字符串频率升序排序
            for (Map.Entry<String, Integer> entry : wordToFreq.entrySet()) {
                pq.offer(entry);
                if (pq.size() > k) {
                    // 维护出现频率最多的k个单词
                    pq.poll();
                }
            }
            // 把出现次数最多的k个字符串返回
            LinkedList<String> res = new LinkedList<>();
            while (!pq.isEmpty()) {
                res.addFirst(pq.poll().getKey());
            }
            return res;
        }
    }

    // 1845. 座位预约管理系统
    // 请你设计一个管理 n 个座位预约的系统，座位编号从 1 到 n 。
    // 请你实现 SeatManager 类：
    // SeatManager(int n) 初始化一个 SeatManager 对象，它管理从 1 到 n 编号的 n 个座位。所有座位初始都是可预约的。
    // int reserve() 返回可以预约座位的 最小编号 ，此座位变为不可预约。
    // void unreserve(int seatNumber) 将给定编号 seatNumber 对应的座位变成可以预约。
    // 示例 1：
    // 输入：
    // ["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"]
    // [[5], [], [], [2], [], [], [], [], [5]]
    // 输出：
    // [null, 1, 2, null, 2, 3, 4, 5, null]
    // 解释：
    // SeatManager seatManager = new SeatManager(5); // 初始化 SeatManager ，有 5 个座位。
    // seatManager.reserve();    // 所有座位都可以预约，所以返回最小编号的座位，也就是 1 。
    // seatManager.reserve();    // 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
    // seatManager.unreserve(2); // 将座位 2 变为可以预约，现在可预约的座位为 [2,3,4,5] 。
    // seatManager.reserve();    // 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
    // seatManager.reserve();    // 可以预约的座位为 [3,4,5] ，返回最小编号的座位，也就是 3 。
    // seatManager.reserve();    // 可以预约的座位为 [4,5] ，返回最小编号的座位，也就是 4 。
    // seatManager.reserve();    // 唯一可以预约的是座位 5 ，所以返回 5 。
    // seatManager.unreserve(5); // 将座位 5 变为可以预约，现在可预约的座位为 [5] 。
    // 基本思路
    // 这题是 379. 电话目录管理系统 的进阶版，那一道题返回的空闲号码可以随意，而这道题要求返回最小的座位编号。
    // 其实很思路是一样的，只是这里需要用到能够按照元素大小自动排序的数据结构
    // 优先级队列（二叉堆），直接看代码吧。
    static class SeatManager {
        // 利用优先级队列自动排序，队头的元素就是最小的
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        public SeatManager(int n) {
            // 初始化所有空闲座位
            for (int i = 1; i <= n; i++) {
                pq.offer(i);
            }
        }

        public int reserve() {
            // 拿出队头元素（最小）
            return pq.poll();
        }

        public void unreserve(int i) {
            pq.offer(i);
        }
    }

    // 295. 数据流的中位数
    // 中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
    //例如 arr = [2,3,4] 的中位数是 3 。
    //例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
    //实现 MedianFinder 类:
    //MedianFinder() 初始化 MedianFinder 对象。
    //void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
    //double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
    //示例 1：
    //输入
    //["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
    //[[], [1], [2], [], [3], []]
    //输出
    //[null, null, null, 1.5, null, 2.0]
    //解释
    //MedianFinder medianFinder = new MedianFinder();
    //medianFinder.addNum(1);    // arr = [1]
    //medianFinder.addNum(2);    // arr = [1, 2]
    //medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
    //medianFinder.addNum(3);    // arr[1, 2, 3]
    //medianFinder.findMedian(); // return 2.0
    static class MedianFinder {
        private PriorityQueue<Integer> large;
        private PriorityQueue<Integer> small;

        public MedianFinder() {
            // 小顶堆
            large = new PriorityQueue<>();
            // 大顶堆
            small = new PriorityQueue<>((a, b) -> {
                return b - a;
            });
        }

        public double findMedian() {
            // 如果元素不一样多，多的那个堆的堆顶元素就是中位数
            if (large.size() < small.size()) {
                return small.peek();
            } else if (large.size() > small.size()) {
                return large.peek();
            }
            // 如果元素一样多，两个堆顶元素的平均数是中位数
            return (large.peek() + small.peek()) / 2.0;
        }

        public void addNum(int num) {
            if (small.size() >= large.size()) {
                small.offer(num);
                large.offer(small.poll());
            } else {
                large.offer(num);
                small.offer(large.poll());
            }
        }

        public static void main(String[] args) {
            MedianFinder medianFinder = new MedianFinder();
            medianFinder.addNum(1);    // arr = [1]
            medianFinder.addNum(2);    // arr = [1, 2]
            medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
            medianFinder.addNum(3);    // arr[1, 2, 3]
            medianFinder.findMedian(); // return 2.0
        }
    }

    // 870. 优势洗牌
    // 给定两个长度相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
    //返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
    //示例 1：
    //输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
    //输出：[2,11,7,15]
    //示例 2：
    //输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
    //输出：[24,32,8,12]
    //提示：
    //1 <= nums1.length <= 105
    //nums2.length == nums1.length
    //0 <= nums1[i], nums2[i] <= 109

    // 基本思路
    // 这题就像田忌赛马的情景，nums1 就是田忌的马，nums2 就是齐王的马，数组中的元素就是马的战斗力，你就是谋士孙膑，请你帮田忌安排赛马顺序，使胜场最多。
    // 最优策略是将齐王和田忌的马按照战斗力排序，然后按照战斗力排名一一对比：
    // 如果田忌的马能赢，那就比赛，如果赢不了，那就换个垫底的来送人头，保存实力。

    static class AdvantageCount {
        public int[] advantageCount(int[] nums1, int[] nums2) {
            int n = nums1.length;
            // 给nums2降序排序
            PriorityQueue<int[]> maxpq = new PriorityQueue<>((int[] pair1, int[] pair2) -> {
                return pair2[1] - pair1[1];
            });
            for (int i = 0; i < n; i++) {
                maxpq.offer(new int[]{i, nums2[i]});
            }
            // 给nums1升序排序
            Arrays.sort(nums1);
            // nums1[left]是最小值，nums1[right]是最大值
            int left = 0;
            int right = n - 1;
            int[] res = new int[n];
            while (!maxpq.isEmpty()) {
                int[] pair = maxpq.poll();
                // maxval是nums2中的最大值，i是对应索引
                int i = pair[0];
                int maxval = pair[1];
                if (maxval < nums1[right]) { // nums1的最大值 > nums2的最大值
                    // 如果nums1[right] 能胜过maxval，那就自己上
                    res[i] = nums1[right];
                    right--;
                } else {
                    // 否则用最小混一下，养精蓄锐
                    res[i] = nums1[left];
                    left++;
                }
            }
            return res;
        }

        public static void main(String[] args) {
            int[] nums1 = new int[]{2, 7, 11, 15};
            int[] nums2 = new int[]{1, 10, 4, 11};
            new AdvantageCount().advantageCount(nums1, nums2);
        }

    }

    // 1834. 单线程CPU
    // 给你一个二维数组 tasks ，用于表示 n 项从 0 到 n - 1 编号的任务。
    // 其中 tasks[i] = [enqueueTime i, processingTime i] 意味着第 i 项任务将会于 enqueueTime i 时进入任务队列，
    // 需要 processingTime i 的时长完成执行。
    // 现有一个单线程 CPU ，同一时间只能执行 最多一项 任务，该 CPU 将会按照下述方式运行：
    // 1. 如果 CPU 空闲，且任务队列中没有需要执行的任务，则 CPU 保持空闲状态。
    // 2. 如果 CPU 空闲，但任务队列中有需要执行的任务，则 CPU 将会选择 执行时间最短 的任务开始执行。
    //    如果多个任务具有同样的最短执行时间，则选择下标最小的任务开始执行。
    // 3. 一旦某项任务开始执行，CPU 在 执行完整个任务 前都不会停止。
    // 4. CPU 可以在完成一项任务后，立即开始执行一项新任务。
    // 返回 CPU 处理任务的顺序。

    // 示例 1：
    //
    // 输入：tasks = [[1,2],[2,4],[3,2],[4,1]]
    // 输出：[0,2,3,1]
    // 解释：事件按下述流程运行：
    // - time = 1 ，任务 0 进入任务队列，可执行任务项 = {0}
    // - 同样在 time = 1 ，空闲状态的 CPU 开始执行任务 0 ，可执行任务项 = {}
    // - time = 2 ，任务 1 进入任务队列，可执行任务项 = {1}
    // - time = 3 ，任务 2 进入任务队列，可执行任务项 = {1, 2}
    // - 同样在 time = 3 ，CPU 完成任务 0 并开始执行队列中用时最短的任务 2 ，可执行任务项 = {1}
    // - time = 4 ，任务 3 进入任务队列，可执行任务项 = {1, 3}
    // - time = 5 ，CPU 完成任务 2 并开始执行队列中用时最短的任务 3 ，可执行任务项 = {1}
    // - time = 6 ，CPU 完成任务 3 并开始执行任务 1 ，可执行任务项 = {}
    // - time = 10 ，CPU 完成任务 1 并进入空闲状态
    // 示例 2：
    //
    // 输入：tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
    // 输出：[4,3,2,0,1]
    // 解释：事件按下述流程运行：
    // - time = 7 ，所有任务同时进入任务队列，可执行任务项  = {0,1,2,3,4}
    // - 同样在 time = 7 ，空闲状态的 CPU 开始执行任务 4 ，可执行任务项 = {0,1,2,3}
    // - time = 9 ，CPU 完成任务 4 并开始执行任务 3 ，可执行任务项 = {0,1,2}
    // - time = 13 ，CPU 完成任务 3 并开始执行任务 2 ，可执行任务项 = {0,1}
    // - time = 18 ，CPU 完成任务 2 并开始执行任务 0 ，可执行任务项 = {1}
    // - time = 28 ，CPU 完成任务 0 并开始执行任务 1 ，可执行任务项 = {}
    // - time = 40 ，CPU 完成任务 1 并进入空闲状态

    // 基本思路
    // 这题的难度不算法，就是有些复杂，难点在于你要同时控制三个变量（开始时间、处理时间、索引）的有序性，而且这三个变量还有优先级
    // 首先应该考虑开始时间，因为只要到了开始时间，任务才进入可执行状态；
    // 其次应该考虑任务的处理时间，在所有可以执行的任务中优先选择处理时间最短的；
    // 如果存在处理时间相同的任务，那么优先选择索引最小的。

    // 所以这道题的思路是：
    // 先根据任务「开始时间」排序，维护一个时间线变量 now 来判断哪些任务到了可执行状态，
    // 然后借助一个优先级队列 pq 对「处理时间」和「索引」进行动态排序。

    // 利用优先级队列动态排序是有必要的，因为每完成一个任务，时间线 now 就要更新，进而产生新的可执行任务。
    static class GetOrder {
        public int[] getOrder(int[][] tasks) {
            int n = tasks.length;
            // 把原始索引也添加上，方便后面排序用
            // 将每个任务转换为三元组 [startTime, processTime, originalIndex]，方便后续排序和记录原始顺序。
            ArrayList<int[]> triples = new ArrayList<>();
            for (int i = 0; i < tasks.length; i++) {
                triples.add(new int[]{tasks[i][0], tasks[i][1], i});
            }
            // 数组先按照任务的开始时间排序
            triples.sort((a, b) -> {
                return a[0] - b[0];
            });
            // 按照任务的处理时间排序，如果处理时间相同，按照原始索引排序
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
                if (a[1] != b[1]) {
                    // 比较处理时间
                    return a[1] - b[1];
                }
                // 比较原始索引
                return a[2] - b[2];
            });
            ArrayList<Integer> res = new ArrayList<>();
            // 记录完成任务的时间线
            int now = 0;
            int i = 0;
            while (res.size() < n) {
                if (!pq.isEmpty()) {
                    // 完成队列中的一个任务
                    // 情况1：队列中有可执行的任务，取出并执行
                    int[] triple = pq.poll();
                    res.add(triple[2]); // 记录任务原始索引
                    // 每完成一个任务，就要推进时间线
                    now += triple[1]; // 时间线推进（当前时间 + 处理时间）
                } else if (i < n && triples.get(i)[0] > now) {
                    // 队列为空可能因为还没到开始时间
                    // 直接把时间线推到最近任务的开始时间
                    // 情况2：队列空且下一个任务未到开始时间，推进时间线到该任务的开始时间
                    now = triples.get(i)[0];
                }
                // 由于时间线的推进，会产生可能开始执行的任务
                // 情况3：将所有已到达开始时间的任务加入队列
                for(; i < n && triples.get(i)[0] <= now; i++){
                    pq.offer(triples.get(i));
                }
            }
            // Java语言特性，将List转化成int[]格式
            int[] arr = new int[n];
            for(int j = 0; j < n; j++){
                arr[j] = res.get(j);
            }
            return arr;
        }

        public static void main(String[] args) {
            int[][] tasks = new int[][]{{1,2},{2,4},{3,2},{4,1}};
//            int[][] tasks = new int[][]{{7,10},{7,12},{7,5},{7,4},{7,2}};
            new GetOrder().getOrder(tasks);
        }
    }
}
